package ShellSort;

import java.util.Random;

//希尔排序
public class sort05 {
    public static void main(String[] args) {
        Random random = new Random();
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(100);
        }
        for (int i : a) {
            System.out.print(i + "   ");
        }
        System.out.println();
        sort(a, a.length);
        for (int ints : a) {
            System.out.print(ints + "   ");
        }
    }

    /*
    public static void sort(int []a,int n)
    {
        int i, j, gap;

        for (gap = n / 2; gap > 0; gap /= 2) //步长
            for (i = 0; i < gap; i++)        //直接插入排序
            {
                for (j = i + gap; j < n; j += gap)
                {
                    if (a[j] < a[j - gap])
                    {
                        int temp = a[j];
                        int k = j - gap;
                        while (k >= 0 && a[k] > temp)
                        {
                            a[k + gap] = a[k];
                            k -= gap;
                        }
                        a[k + gap] = temp;
                    }
                }
            }
        }
    }
    */
    public static void sort(int[] a, int n) {
        int j, gap;

        for (gap = n / 2; gap > 0; gap /= 2)
            for (j = gap; j < n; j++) {//从数组第gap个元素开始
                if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
                {
                    int temp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > temp) {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = temp;
                }
            }
    }
}
    /*public static void sort(int[] a, int n) {
        {
            int i, j, gap;

            for (gap = n / 2; gap > 0; gap /= 2)
                for (i = gap; i < n; i++)
                    for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
                    {
                        int t=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=t;
                    }
        }
    }
    */


